package leetcode_2701_2800;

import java.util.Arrays;

public class LeeCode_2719 {
    public static void main(String[] args) {
        System.out.println(count("6312", "9416", 29, 30));
    }
    private static int count(String num1, String num2, int min_sum, int max_sum) {
        int mod = (int) (1e9 + 7);
        int ans = count(num2, min_sum, max_sum) - count(num1, min_sum, max_sum) + mod;
        int sum = 0;
        for (int i = 0; i < num1.length(); i++) {
            sum += num1.charAt(i) - '0';
        }
        if (sum >= min_sum && sum <= max_sum){
            ans++;
        }
        return ans % mod;
    }
    private static int count(String num, int min, int max){
        int n = num.length();
        char[] s = num.toCharArray();
        int[][] memo = new int[n][Math.min(n * 9, max) + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }
        return f(s, memo, 0, 0, true, min, max);
    }
    private static int f(char[] s, int[][] memo, int i, int sum, boolean isLimit, int min, int max) {
        int mod = (int) (1e9 + 7);
        if (sum > max)
            return 0;
        if (i == s.length)
            return sum >= min ? 1 : 0;
        if (!isLimit && memo[i][sum] != -1)
            return memo[i][sum];
        int up = isLimit ? s[i] - '0' : 9, res = 0;
        for (int j = 0; j <= up; j++) {
            res += f(s, memo, i + 1, sum + j, isLimit && j == up, min, max);
            res %= mod;
        }
        if (!isLimit)
            memo[i][sum] = res;
        return res;
    }
}
